// m

// 给定一个链表的头节点head，链表中每个节点除了next指针之外，还包含一个随机指针random，该指针可以指向链表中的任何节点或者空节点
// 要求将该链表进行深拷贝，返回复制链表的头节点

// 思路： 迭代
// 1. 遍历链表，利用哈希表，以旧节点：新节点 为映射关系，将节点关系存储下来
// 2. 再次遍历链表，将新链表的next和random指针设置好

function Node(val, next, random) {
    this.val = val;
    this.next = next;
    this.random = random;
};
function copyRandomList(head) {
    if (!head) {
        return null
    }
    let map = new Map()
    let curr = head
    while (curr) {
        let new_node = new Node(curr.val, null, null)
        map.set(curr, new_node)
        curr = curr.next
    }
    curr = head

    while (curr) {
        if (curr.next) {
            map.get(curr).next = map.get(curr.next)
        }
        if (curr.random) {
            map.get(curr).random = map.get(curr.random)
        }
        curr = curr.next
    }

    return map.get(head)
}